The present invention is directed to a method for optimizing data compression while also improving throughput. More particularly, the present invention is directed to a method for interleaving arithmetic codes with other codes or unencoded data to provide an optimal combination of compression and throughput.
As people seek to communicate more and more frequently in the digital domain, that is transferring digital data between a source and a receiver, a limiting factor is the availability of channel resources. Channels typically are provided with a predetermined bandwidth based on the physical characteristics of the channel itself. To therefore increase the overall information throughput along the channel, it is beneficial to provide capabilities by which information can be transmitted through the channel utilizing the least amount of bandwidth possible.
FIG. 1 illustrates an example of a prior art configuration for transmitting data from a source to a receiver which keeps this goal in mind. In particular, source information, which ultimately could be in analog form and has been digitized by some analog to digital converter (not shown) is provided to a compression device 101. The compression device operates on the digital bit stream to reduce the number of bits needed to represent the information received from the source. Such information can take the form of a bit stream that is representative of some event, that is, for example, letters in text or pixels in an image. The compressed data is then provided to an encryption device 102 which can "scramble" the data to make it unusable by anyone who is not aware of both the encryption technique and the encryption key. This safeguards the data from being taken off of the channel by some third party and used without permission of the source. The encrypted data is provided to an error correction code (ECC) generator. This ECC generator provides additional information based on the encrypted data so as to permit the receiver to reconstruct data even where some limited number of errors occur in the course of the transmission of the data from the source to the receiver. The data is then provided to the channel 104. At a receiving end the data is then passed to a device referred to as "ECC decoder" 105 which uses the transmitted error correction code information to present a corrected data bit stream to the decryption device 106. The decryption device then deciphers the received data based on some encryption key to essentially provide to the decompression device 107 the same data bit stream which was provided from the compression device 101 to the encryption device 102. The decompression device thus takes what amounts to be the compressed data bit stream and expands it for use by the receiver (not shown).
FIGS. 2A and 2B are block diagram representations of portions of the compression device and the decompression device of FIG. 1, respectively. In FIG. 2A the compression device may include an encoder modeler 201 and a coder 202. In this context the modeler and the coder will both receive the digital representation of events. The modeler will provide probabilities with respect to the events, for example, the probability that the letter "u" will follow the letter "q", to the coder. The coder takes this probability and based on the nature of the coder tries to produce a bit stream with the fewest bits possible.
FIG. 2B relates to what transpires at the receiver in the decompression module. In this instance, the coded bit stream is provided to the decoder 204. Again, the modeler 203 provides probability information to the decoder so that the decoder can take the coded bit stream and provide a stream of decoded events to the receiver as well as feeding the events back to the modeler. Such modelers are well known in the art.
Sometimes it may be desirable to use different codes in the same application and to have the output from the different coders appear in the same coded bit stream. One way to insure decodability is to have the encoder arrange the bits and the coded bit stream so that the decoder, by reading bits sequentially, will automatically extract those bits it needs, exactly when it needs them. This mechanism is called decoder-synchronized encoding. This technique has been described in literature, for example, "Bi-Level Image Coding with Melcode-Comparison of Block-Type Code and Arithmetic-Type Code", Ono et al., proceedings IEEE Global Telecommunications Conference, November 1989.
The prior art specifically describes interleaving codes referred to as run-length codes. These codes are based on the notion of producing a bit stream that represents how many occurrences in a row there are of more probable events. One example of such a run length code is referred to as a Golomb code described in "Run-Length Encodings", Golomb, IEEE Trans. Inform Theory IT-12, (July 1966), 399-401.
Run-length codes are one example of codes that might be used in an entropy encoder. Run-length codes provide more coding speed with a small amount of memory required. There are other types of entropy encoders known in the art.
For example, it is known to code data using Huffman codes. See "A Method for the Construction of Minimum Redundancy Codes", Huffman, Proceedings of the Institute of Radio Engineers, V.40, D. 1952, pp 1098-1101. These codes have the advantage that they are fast and are prefix codes. The disadvantage with Huffman codes is that they are sub-optimal, especially for events with high probabilities and do not handle binary alphabets. In addition, adaptive coding using Huffman codes tends to be slow.
Another known coding technique is arithmetic coding. Arithmetic coding is generally described in "Arithmetic Coding for Data Compression" by Howard et al., Proceedings of the IEEE, Vol. 82, No. 6, June 1994, pages 857-865. The disclosure of this paper is hereby incorporated by reference. Another reference describing arithmetic coding is "Arithmetic Coding for Data Compression" by Witten et al., Communications of the ACM, June 1987, Vol. 30, No. 6, pages 521-540. This second paper describes one of the available arithmetic codes commonly referred to as Witten-Neal-Cleary coding. For purposes of this discussion, it is helpful to review an example of an arithmetic code and the incremental coding with carry control will be used for this purpose. In theory, arithmetic codes assign one "codeword" to each possible data set. The codewords consist of half-open sub-intervals of the half-open unit interval 0,1) and are expressed by specifying enough bits to distinguish the sub-interval corresponding to the actual data set from all other possible sub-intervals. Shorter codes correspond to larger sub-intervals and thus more probable input data sets. In practice, the sub-interval is refined incrementally using the probabilities of the individual events with bits being output as soon as they are known.
A basic description of how arithmetic coding works is provided with reference to FIGS. 3A and 3B which are related to an implementation of the incremental or Witten-Neal-Cleary coding. First, an initial current interval is defined 0, 1), step 300. Then in step 301 this initial interval is subdivided based on the probabilities associated with the first event. In the present example, assume that the first event is either a1 (with probability P {a1}=2/3) or b1 (with probability P {b1}=1/3); the second event is a2 (with probability P {a2}=1/2) or b2 (with probability P {b2}=1/2); and the third event is a3 (with probability P {a3}=3/5) or b3 (with probability P {b3}=2/5) . The actual file to be encoded in this example is the sequence b1a2b3. Thus, in the step of subdividing with respect to the first event, the interval is subdivided into subintervals corresponding to the probability of al, that is, from 0 to 2/3 and the probability of b1, that is, from 2/3 to 1. In step 302, the coder then checks the input and determines it to be b1. This is identified as being in the b1 region so the subinterval 2/3, 1) is selected. According to the coding technique a plurality of interval coding rules are referred to in step 303 to determine what output, if any should be provided based on the location of the input within the particular subintervals. In this particular coding mechanism the rules are as follows:
1. if the designated or selected sub-interval lies entirely within 1/4, 3/4) the coder keeps track of this fact for future output by incrementing a follow count and then doubles the size of the sub-interval by linearly expanding 1/4, 3/4), to (0, 1); PA1 2. if the selected sub-interval lies entirely within 0, 1/2), the coder outputs 0 and any following 1's left over from the previous events, then the sub-interval is doubled in size by linearly expanding 0, 1/2) to 0, 1); PA1 3. if the new sub-interval lies entirely within 1/2 , 1), the coder outputs 1 and any following 0's left over from previous events, then the coder doubles the size of the sub-interval by linearly expanding 1/2, 1) to 0, 1); and PA1 4. if the new sub-interval is not entirely within one of the intervals 0, 1/2 !, 1/4,3/4!, or 1/2,1! then the coder exits the loop.
Now turning to our more specific example, as shown in FIG. 3A, once it is determined that the first event is b1, the interval coding rules are applied in step 303. If this new sub-interval does not fall entirely within one of the three ranges defined above, namely 0, 1/2 ), 1/4, 3/4), or 1/2, 1) then the system would exit the loop. This step is represented in FIG. 3B where it is determined whether the new sub-interval is entirely within a predefined range in step 304. If it is not within one of these predefined ranges then the process resumes with step 301 for the next event. In the present example, however the interval for b1, 2/3 to 1, is entirely within the interval 1/2, 1) so that 1 is immediately output and the sub-interval is doubled in size by linearly expanding so that the new sub-interval runs from 1/3 to 1. This constitutes the expansion of the sub-interval required by step 306. Then steps 303 through 306 are repeated until the test in step 304 returns "NO", in which case the process returns to step 301. Namely, the expanded sub-interval is subdivided using the probabilities of the second event. Since a2 and b2 each have an equal probability of occurring, that is 1/2, the interval is subdivided into two sub-intervals 1/3 to 2/3, and 2/3 to 1. In the example sequence the second event is a2 and so the sub-interval 1/3 to 2/3 is selected as shown in FIG. 3A. Since this sub-interval straddles 1/3, that is, the interval lies entirely within 1/4,3/4) the coder keeps track of this fact for future output by incrementing a follow count and expands the sub-interval, doubling it, see 309 in FIG. 3A. In this circumstance, the interval is expanded to 1/6, 5/6!. Once the sub-interval has been expanded to 1/6, 5/6! the new expanded sub-interval is subdivided in accordance with the probabilities associated with a3 and b3, namely a first subinterval of 1/6, 17/30! and a second subdivided interval 17/30, 5/6!. The input event, namely b3, is received and the appropriate subinterval is selected. Since this interval is entirely within 1/2, 1) the coder outputs a 1 and any following 0s left over from the previous events. Since there was one follow then the output is 10. The last interval is then expanded to 2/15, 2/3) Since all binary numbers that start with 0.01 are within this range, outputting 01 suffices to uniquely the range. As a consequence the encoded output for the event sequence b1 is 11001.
Arithmetic coding gives theoretical optimal compression and does not depend on a particular type of probability assignment. However, creating coding intervals requires multiplication and division which can be expensive and slow, especially by comparison to Huffman codes. Circumstances may arise where it would be beneficial to use arithmetic coding on one part of source data and some other code, for example, a Huffman code or identity code on another part. This is especially true where the source data consists of a stream of highly skewed and not-so-skewed data. Since the arithmetic code is slower it is preferable to avoid using the arithmetic coder with respect to not-so-skewed data reserving it only for highly skewed data. In one example of a potential data source, data to be coded using a system for compressing bi-level image data using pattern matching consists of approximately 1/2 highly skewed probability data and approximately 1/2 non-highly skewed data. Thus, it would be desirable if one could encode only part of the source data with the arithmetic encoder. In fact, it would be desirable to interleave arithmetic coding with either some other coding such as prefix coding or no coding at all thereby optimizing both the compression, using arithmetic coding on highly skewed data, and throughput, which is negatively influenced if arithmetic coding is otherwise used on non-highly skewed data.